package solution;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author zhangmin
 * @create 2021-10-07 11:20
 */
public class Solution_6DP_Subseq {

    /*===========================================================================================================================
     *DP 子序列问题 516. 最长回文子序列
     *  dp 数组的定义是：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]
     * dp[i][j] = 1,(i == j)
     * dp[i][j] = dp[i + 1][j - 1] + 2， s[i] == s[j]
     *  dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])， s[i] ！= s[j]
     *  */
    public int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i],0);
            dp[i][i]=1;
        }
        // 反着遍历保证正确的状态转移
        for (int i = n-2; i >=0 ; i--) {
            for (int j = i+1; j < n; j++) {
                if (s.charAt(i)==s.charAt(j))
                    dp[i][j]=dp[i+1][j-1]+2;
                else
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
    //状态压缩
    public int longestPalindromeSubseq1(String s) {
        int n=s.length();
        int[] dp=new int[n];
        // 一维 dp 数组全部初始化为 1
        Arrays.fill(dp,1);
        for (int i = n-2; i >=0 ; i--) {
            int pre=0;
            for (int j = i+1; j < n; j++) {
                //在此处还没有赋新值，此时的dp[j]对应二维 dp 数组中 dp[i+1][j] 的位置，dp[j-1]是内层循环计算的新值，对应二维 dp 数组中 dp[i][j-1] 的位置
                int temp=dp[j];//此时dp[j]存储的就是二位dp[i+1][j]，之后会被dp[i][j]覆盖，所以先记录下来
                if (s.charAt(i)==s.charAt(j))
                    dp[j]=pre+2;
                else
                    dp[j]=Math.max(dp[j],dp[j-1]);
                pre=temp;//在此处记录，在下一轮的内层循环种相当于dp[i+1][j-1]
            }
        }
        return dp[n-1];
    }


    /*===========================================================================================================================
     *DP 子序列问题 72. 编辑距离
     * 1.递归+备忘录：定义：dp(i, j) 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
     *  */
    int[][] memo72;
    public int minDistance(String word1, String word2) {
        memo72=new int[word1.length()][word2.length()];
        return dp72(word1,word2,word1.length()-1,word2.length()-1);
    }

    int dp72(String s1,String s2,int i,int j){

        if (i==-1)
            return j+1;
        if (j==-1)
            return i+1;
        if (memo72[i][j]!=0)
            return memo72[i][j];

        if (s1.charAt(i)==s2.charAt(j)){
            memo72[i][j]=dp72(s1,s2,i-1,j-1);// 本来就相等，不需要任何操作,s1[0..i] 和 s2[0..j] 的最小编辑距离等于s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
        } else {
            memo72[i][j]=Math.min(dp72(s1,s2,i-1,j)+1,Math.min(dp72(s1,s2,i,j-1)+1,dp72(s1,s2,i-1,j-1)+1));
            //dp(i, j - 1) + 1,    插入:直接在 s1[i] 插入一个和 s2[j] 一样的字符,那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
            //dp(i - 1, j) + 1,    删除: 直接把 s[i] 这个字符删掉,前移 i，继续跟 j 对比,操作数加一
            //dp(i - 1, j - 1) + 1  替换:直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了,同时前移 i，j 继续对比,操作数加一
        }
        return memo72[i][j];
    }
    /*
     *2.dp Table :dp[i-1][j-1]:存储 s1[0..i] 和 s2[0..j] 的最小编辑距离 --dp 函数的 base case 是 i,j 等于 -1，而数组索引至少是 0，所以 dp 数组会偏移一位。
     * dp[i][0] = i;
     *  dp[0][j] = j;
     * dp[i][j] = dp[i - 1][j - 1], s1[i]==s2[j]
     * dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j - 1] + 1,dp[i-1][j-1] + 1),s1[i]!=s2[j]
     * */
    public int minDistance1(String word1, String word2) {
        int n1=word1.length();
        int n2=word2.length();
        int[][] dp=new int[n1+1][n2+1];
        for (int i = 1; i <=n1 ; i++) {
            dp[i][0]=i;
        }
        for (int j = 1; j <=n2 ; j++) {
            dp[0][j]=j;
        }
        for (int i = 1; i <=n1 ; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                }
            }
        }
        return dp[n1][n2];
    }

    /*===========================================================================================================================
     *DP 子序列问题 300. 最长递增子序列
     * 1. dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
     * 时间复杂度 O(N^2)
     *  */
    public int lengthOfLIS1(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        Arrays.fill(dp,1);
        for (int i = 0; i <n ; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res=0;
        for (int d:dp ) {
            res=Math.max(res,d);
        }
        return res;
    }
    /*
     * 2.二分查找：
     * 依据扑克规则：只能把点数小的牌压到点数比它大的牌上；如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去；
     * 如果当前牌有多个堆可供选择，则选择最左边的那一堆放置。
     * 按照这种规则最后牌堆数就是lis的最大长度
     * */
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[] top=new int[n];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < n; i++) {
            //待处理的元素
            int p=nums[i];
            /***** 搜索左侧边界的二分查找 *****/
            int l=0,r=piles;
            while (l<r){
                int mid=(l+r)/2;
                if (top[mid]<p){
                    l=mid+1;
                }else {
                    r=mid;
                }
            }
            // 没找到合适的牌堆，新建一堆
            if (l==piles)
                piles++;
            top[l]=p;
        }
        return piles;
    }



    /*===========================================================================================================================
     *DP 子序列问题 354. 俄罗斯套娃信封问题
     *先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序(因为两个宽度相同的信封不能相互包含的，逆序排序保证在 w 相同的数对中最多只选取一个)。
     * 之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。
     * 此算法的时间复杂度为 O(NlogN),空间复杂度为 O(N)，因为计算 LIS 的函数中需要一个 top 数组。
     *  */
    public int maxEnvelopes(int[][] envelopes) {
        int n=envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0];
            }
        });

        /*---------对高度h进行LIS的求解-------------*/
        int[] top=new int[n];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < n; i++) {
            //待处理的元素
            int p=envelopes[i][1];
            /***** 搜索左侧边界的二分查找 *****/
            int l=0,r=piles;
            while (l<r){
                int mid=(l+r)/2;
                if (top[mid]<p){
                    l=mid+1;
                }else {
                    r=mid;
                }
            }
            // 没找到合适的牌堆，新建一堆
            if (l==piles)
                piles++;
            top[l]=p;
        }
        return piles;
    }

    /*===========================================================================================================================
     *DP 子序列问题 53. 最大子序和
     *dp[i]表示以 nums[i] 为结尾的「最大子数组和」
     * dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); 选择要不要与前一个连接组成一个
     *  */
    public int maxSubArray1(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        dp[0]=nums[0];
        int res=dp[0];
        for (int i = 1; i < n; i++) {
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            res=Math.max(res,dp[i]);
        }
        return res;
    }
    //状态压缩
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int dp_0=nums[0];
        int dp_1=0;
        int res=dp_0;
        for (int i = 1; i < n; i++) {
            dp_1=Math.max(dp_0+nums[i],nums[i]);
            dp_0=dp_1;
            res=Math.max(res,dp_1);
        }
        return res;
    }

    /*===========================================================================================================================
     *DP 子序列问题 1143. 最长公共子序列
     * 1.递归+备忘录
     *  */
    // 备忘录，消除重叠子问题
    int[][] memo1143;
    public int longestCommonSubsequence1(String text1, String text2) {
        memo1143=new int[text1.length()][text2.length()];
        for (int[] m:memo1143) {
            Arrays.fill(m,-1);
        }
        return dp1143(text1,0,text2,0);
    }
    // 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
    int dp1143(String s1, int i, String s2, int j) {
        if (i==s1.length()||j==s2.length())
            return 0;
        if (memo1143[i][j]!=-1){
            return memo1143[i][j];
        }
        if (s1.charAt(i)==s2.charAt(j)){
            // s1[i] 和 s2[j] 必然在 lcs 中
            memo1143[i][j]=dp1143(s1,i+1,s2,j+1)+1;
        }else {
            // s1[i] 和 s2[j] 至少有一个不在 lcs 中
            memo1143[i][j]=Math.max(dp1143(s1,i+1,s2,j),dp1143(s1,i,s2,j+1));
        }
        return memo1143[i][j];
    }
    /*2.dp table:dp[i][j]表示s1[0...i-1]与s2[0...j-1]的最长公共子序列长度*/
    public int longestCommonSubsequence(String text1, String text2) {
        int n=text1.length();
        int m=text2.length();
        int[][] dp=new int[n+1][m+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                if (text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }


    /*===========================================================================================================================
     *DP 子序列问题 583. 两个字符串的删除操作
     * 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
     * 题目让我们计算将两个字符串变得相同的最少删除次数,删除的结果即为它俩的最长公共子序列
     *  */
    public int minDeleteDistance(String word1, String word2) {
        int n=word1.length(),m=word2.length();
        int[][] dp=new int[n+1][m+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return n-dp[n][m]+m-dp[n][m];
    }
    /*===========================================================================================================================
     *DP 子序列问题 712. 两个字符串的最小ASCII删除和
     *给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
     *  */
    int[][] memo712;
    public int minimumDeleteSum(String s1, String s2) {
        memo712=new int[s1.length()][s2.length()];
        for (int[] m:memo712) {
            Arrays.fill(m,-1);
        }
        return dp712(s1,0,s2,0);
    }
    // 定义：计算 s1[i..] 和 s2[j..] 的最小ASCII删除和
    int dp712(String s1, int i, String s2, int j) {
        int res = 0;
        if (i==s1.length()){
            // 如果 s1 到头了，那么 s2 剩下的都得删除
            for (; j < s2.length(); j++) {
                res+=s2.charAt(j);
            }
            return res;
        }
        if (j==s2.length()){
            // 如果 s2 到头了，那么 s1 剩下的都得删除
            for (; i < s1.length(); i++) {
                res+=s1.charAt(i);
            }
            return res;
        }
        if (memo712[i][j]!=-1){
            return memo712[i][j];
        }
        if (s1.charAt(i)==s2.charAt(j)){
            // s1[i] 和 s2[j] 必然在 lcs 中
            memo712[i][j]=dp712(s1,i+1,s2,j+1);
        }else {
            // s1[i] 和 s2[j] 至少有一个不在 lcs 中
            memo712[i][j]=Math.min(dp712(s1,i+1,s2,j)+s1.charAt(i),dp712(s1,i,s2,j+1)+s2.charAt(j));
        }
        return memo712[i][j];
    }


    public static void main(String[] args) {

        String s1="horse";
        String s2="ros";

        Solution_6DP_Subseq object=new Solution_6DP_Subseq();
        System.out.println(object.minDistance1(s1,s2));
    }
}
